#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> gRes;
int gN;

//
// 通用框架
// 
// nId      当前节点ID
// vnVal    当前节点取值的可能性，每个节点可能不一样。实际上搞成一样会简单一点，通过IsValid去剪枝。
// vnPath   当前遍历已经选择，当前待验证的选择
//
// g_vnResult 全局
//
void Backtrack(int nId, vector<int> &vnVal, vector<int> &vnPath) {
    if (NeedToCollect(nId, vnPath)) {
        CollectResult(nId, vnPath);
    }
    if (IsDeadNode(nId, vnPath)) {
        return;
    }
    for (auto val : vnRange) {
        if (false == IsFeasible(nId, val)) {
            continue;
        }
        Select(nId, val);
        Backtrack(GetNext(nId), vnRange, vnPath);
        Unselect(nId, val);
    }
}

//
// backtrackA
//

bool isSolutionA(vector<int> &path) {
    return true; // always be true
}

void recordResultA(vector<int> &path) {
    gRes.push_back(path);
}

bool isValidA(vector<int> &path, int idxNext) {
    if (path.size() == 0) {
        return true;
    }
    if (idxNext > path.back()) {
        return true;
    } else {
        return false;
    }
}

void doSelectionA(vector<int> &path, int idxNext) {
    path.push_back(idxNext);
}

void undoSelectionA(vector<int> &path, int idxNext) {
    path.pop_back();
}

void backtrackA(vector<int> path, vector<int> choices) {
    if (isSolutionA(path)) {
        recordResultA(path);
        // return;
    }

    // try to select one
    for (auto idx : choices) {
        if (isValidA(path, idx)) // prunning
        {
            doSelectionA(path, idx);   // selection
            backtrackA(path, choices); // judge if we find one solution
            undoSelectionA(path, idx); // de-selection
        }
    }
}

//
// backtrackB
//

bool isSolutionB(vector<int> &path) {
    if (path.size() == gN) {
        return true;
    } else {
        return false;
    }
}

void recordResultB(vector<int> &path) {
    gRes.push_back(path);
}

bool isValidB(vector<int> &path, int idxNext) {
    for (auto idx : path) {
        if (idx == idxNext) {
            return false;
        }
    }

    return true;
}

void doSelectionB(vector<int> &path, int idxNext) {
    path.push_back(idxNext);
}

void undoSelectionB(vector<int> &path, int idxNext) {
    path.pop_back();
}

void backtrackB(vector<int> path, vector<int> choices) {
    if (isSolutionB(path)) {
        recordResultB(path);
        // return;
    }

    // try to select one
    for (auto idx : choices) {
        if (isValidB(path, idx)) // prunning
        {
            doSelectionB(path, idx);   // selection
            backtrackB(path, choices); // judge if we find one solution
            undoSelectionB(path, idx); // de-selection
        }
    }
}

//
// backtrackC
//

bool isSolutionC(vector<int> &path) {
    if (path.size() == gN) {
        return true;
    } else {
        return false;
    }
}

void recordResultC(vector<int> &path) {
    gRes.push_back(path);
}

bool isValidC(vector<int> &path, int idxNext) {
    int currentRow = path.size();
    int row = 0;
    for (auto idx : path) {
        if (idx == idxNext) {
            return false;
        }

        // 45 degree judge
        if (idxNext == (idx + (currentRow - row))) {
            return false;
        }
        // 45 degree judge
        if (idxNext == (idx - (currentRow - row))) {
            return false;
        }
        row++;
    }
    return true;
}

void doSelectionC(vector<int> &path, int idxNext) {
    path.push_back(idxNext);
}

void undoSelectionC(vector<int> &path, int idxNext) {
    path.pop_back();
}

void backtrackC(vector<int> path, vector<int> choices) {
    if (isSolutionC(path)) {
        recordResultC(path);
        // return;
    }

    // try to select one
    for (auto idx : choices) {
        if (isValidC(path, idx)) // prunning
        {
            doSelectionC(path, idx);   // selection
            backtrackC(path, choices); // judge if we find one solution
            undoSelectionC(path, idx); // de-selection
        }
    }
}

//
// output and main
//

void output(string name) {
    printf("\n%s:\n", name.c_str());
    for (auto myList : gRes) {
        for (auto idx : myList) {
            printf("%d ", idx);
        }
        printf("\n");
    }
    printf("\n");
}

int main(void) {
    vector<int> path;
    gN = 5;

    // 创建一个包含 1 到 n 的整数列表
    std::vector<int> choices = std::vector<int>(gN);
    for (int i = 0; i < gN; ++i) {
        choices[i] = i + 1;
    }

    // 组合问题(没有定义seletion/unselection)
    gRes.clear();
    path.clear();
    printf("choices: %d %d\n", choices.size(), choices[2]);
    backtrack(0, path);
    output("non-standard dict");

    // 组合问题(顺序无关)
    gRes.clear();
    path.clear();
    printf("choices: %d %d\n", choices.size(), choices[2]);
    backtrackA(path, choices);
    output("standard dict");

    // 排列问题(顺序相关)
    gRes.clear();
    path.clear();
    printf("choices: %d %d\n", choices.size(), choices[2]);
    backtrackB(path, choices);
    output("standard pernitration");

    // 八皇后问题
    gRes.clear();
    path.clear();
    printf("choices: %d %d\n", choices.size(), choices[2]);
    backtrackC(path, choices);
    output("standard queen 8");
    printf("queen8 %d\n", gRes.size());

    return 0;
}
